package com.leecode.exercise;

/**
 * @ClassName LeeCode_147_OrderList
 * @Author bsy
 * @Description 147. 对链表进行插入排序
 * 输入: head = [4,2,1,3]
 * 输出: [1,2,3,4]
 * @Date 2022/6/27 21:56
 * @Version 1.0
 */
public class LeeCode_147_OrderList {
    public static void main(String[] args) {
        //输入: head = [4,2,1,3]
        //输出:        [1,2,3,4]
        ListNode head = new ListNode(4);
        head.next = new ListNode(2);
        head.next.next = new ListNode(1);
        head.next.next.next = new ListNode(3);
        ListNode listNode = new Solution6().insertionSortList(head);
        /*while (listNode != null){
            System.out.println(listNode.val);
        }*/

    }
}


class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}


class Solution6 {
    public ListNode insertionSortList(ListNode head) {
        ListNode dummyHead = new ListNode(0, head);
        ListNode end = head;
        while (end.next != null) {
            if (end.val <= end.next.val) {
                end = end.next;
            } else {
                ListNode prev = dummyHead, next = end.next;
                while (prev.next.val <= next.val) {
                    prev = prev.next;
                }
                end.next = next.next;
                next.next = prev.next;
                prev.next = next;
            }
        }
        return dummyHead.next;
    }

}

